package Offer;

/*
* 矩阵中的路径
* */
public class Offer12exist {
    public boolean exist(char[][] board, String word) {
        int m=board.length;
        int n=board[0].length;
        int[][] visit=new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                 if(dfs(board,word,i,j,0,visit)){
                     return true;
                 }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int i, int j, int k,int[][] visit) {
        if(i<0 || i>=board.length || j<0 || j>=board[0].length || board[i][j]!=word.charAt(k) || visit[i][j]==1){
            return false;
        }
        if(k==word.length()-1){
            return true;
        }
        visit[i][j]=1;
        boolean res=dfs(board, word, i-1, j, k+1, visit) || dfs(board, word, i, j-1, k+1, visit) ||
                    dfs(board, word, i+1, j, k+1, visit) || dfs(board, word, i, j+1, k+1, visit);
        visit[i][j]=0;
        return res;
    }
}
